#include <iostream>
#include <vector>
using namespace std;

class Solution {
        const int MOD = 1e9 + 7;
    public:
	int methods(vector<int> &group, vector<int> &profit, int w, int n, int res)
	{
		if (n <= 0) {
			return res <= 0 ? 1 : 0;
		}

		if (w < 0) {
			return res <= 0 ? 1 : 0;
		}

		int p1 = methods(group, profit, w - 1, n, res);
		int p2 = 0;
		if (n >= group[w]) {
			p2 = methods(group, profit, w - 1, n - group[w], res - profit[w]);
		}

		return p1 + p2;
	}

	int methods_dp(vector<int> &group, vector<int> &profit, int r, int m)
	{
		int n = group.size();
		vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(r + 1, vector<int>(m + 1, 0)));
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= r; j++) {
				dp[i][j][0] = 1;
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= r; j++) {
				for (int k = 0; k <= m; k++) {
					dp[i][j][k] = dp[i - 1][j][k];
					if (j >= group[i - 1]) {
						int s = max(0, k - profit[i - 1]);
						int l = j - group[i - 1];
						dp[i][j][k] =  (dp[i][j][k] +  dp[i - 1][l][s])%MOD;
					}
				}
			}
		}

		return dp.back().back().back();
	}

        int methods_dp_sp(vector<int> &group, vector<int> &profit, int r, int m)
        {
                int n = group.size();
                vector<vector<int>> dp(r + 1, vector<int>(m + 1, 0));
                for(int i = 0; i <= r; i++){
                        dp[i][0] = 1;
                }

                for(int i = n - 1; i >= 0; i--){
                        for(int j = r; j >= 0; j--){
                                for(int k = m; k >= 0; k--){
                                        int p1 = dp[j][k];
                                        int p2 = group[i] <= j ? dp[j - group[i]][max(0, k - profit[i])] : 0;
                                        dp[j][k] = (p1 + p2) % MOD;
                                }
                        }
                }
                return dp.back().back();
        }

	int profitableSchemes(int n, int minProfit, vector<int> &group, vector<int> &profit)
	{
		return methods_dp(group, profit, n, minProfit);
	}
};

int main()
{
	int n = 5, minProfit = 3;
	vector<int> group = { 2, 2 }, profit = { 2, 3 };
	cout << Solution().profitableSchemes(n, minProfit, group, profit) << endl;
	return 0;
}